\documentclass[a4paper,11pt]{article}

\usepackage{graphicx}
\usepackage[ansinew]{inputenc}
\usepackage[spanish]{babel}
\usepackage{multirow}
\usepackage{fancyhdr}


% Titulo del Trabajo Practico.
\title{ Trabajo Practico 1   \\
        \large{ 66.20 Organizacion de las Computadoras } }


\sloppy
\date{}


\begin{document}

\maketitle
\thispagestyle{empty}   % quita el numero en la primer pagina
%\renewcommand{\labelenumi}{\alph{enumi}.}

\section{Objetivos}

Familiarizarse con el conjunto de instrucciones MIPS32 y el concepto de ABI 1 , escribiendo un programa portable que resuelva el problema descripto en el enunciado.


\section{Introduccion}
De la forma que nosotros lo planteamos, la optimizacion es que se le pueden hacer a un codigo ya escrito, se dividen en dos grupos. Uno seria, aplicar las optimizaciones directamente sobre el codigo \texttt{C}, como desenrollando bulces, asignar valiables a registros etc. Dentro del otro grupo, las optimizaciones de hacen a mas bajo nivel, es decir en leguaje simbolico. Esta ultima optimizacion genera una dependecia directa entre el codigo y la arquitectura donde este se va a ejecutar.
\section{Desarrollo}

El programa realizado se trata de una version en lenguaje C del Algoritmo de Euclides. El programa recibira por stdin dos numeros enteros no signados, y dara por stdout(o escribira en un archivo) el maximo comun divisor de estos. De haber errores, los mensajes de error deberan salir exclusivamente por stderr.



\newpage

\section{Opciones}

\begin{itemize}
\item	``-h'' o ``--help'':    Prints usage information.
\item	``-V'' o ``--version'': Prints version information.
\item	``-o'' o ``--output'':  Path to output file.
\end{itemize}


\section{Proceso y salida}

El archivo main.c implementa la validez de los datos de entrada y parametros externos del programa.
Para el caso que sea '-o' se verifica si sera por stdout porque como 3er parametro se paso '-' o la correcta apertura del archivo en el caso de que este parametro sea una ruta de archivo.
El programa retornara error si su cuarto argumento esta fuera de rango [2, MAXINT].
Asi como la llamada a la funcion implementada en assembly, la cual calculara el maximo comun divisor.
En caso de no haber ningun error, el programa devuelve cero, y resulto con exito.

\newpage
\section{Pruebas}


Luego de generar el codigo compilamos en el sistema operativo simulado con las siguiente lineas:\\
\\\texttt{
	\$gcc -Wall -ggdb -O0 -c -o main.o main.c 
	\\
	\$gcc -Wall -ggdb -O0 -c -o eucl\_it.o eucl\_it.s
	\\
	\$gcc -Wall -ggdb -O0 -c -o eucl\_rec.o eucl\_rec.s}
	
	Una vez compilados los dos modulos, los linkeamos de la siguiente manera:\\
\texttt{\$gcc -Wall -ggdb -O0 -o eucl\_it eucl\_it.o main.o}

\texttt{\$gcc -Wall -ggdb -O0 -o eucl\_rec eucl\_rec.o main.o}

\begin{itemize}
\item	Wall: activa todos los mensajes de warning.

\item	O: indica el nivel de optimizacion, en este caso no queremos que el compilador optimice el programa por lo que ponemos nivel 0.

\item	ggdb: compila el archivo con informacion de debuggeo para que sea posible correr el programa en modo debug, por ejemplo, con el gdb.

\item	o: genera el archivo de salida.

\end{itemize}

Habiendo generado el ejecutable procedimos a realizar las pruebas para los valores (5, 10), (256, 192), (1111, 1294)

\begin{verbatim}
root@:~/tp# ./eucl_it -o - 5 10
result: 5
root@:~/tp# ./eucl_it -o - 256 192
result: 64
root@:~/tp# ./eucl_it -o - 1111 1294
result: 1
root@:~/tp# ./eucl_rec -o - 5 10
result: 5
root@:~/tp# ./eucl_rec -o - 256 192
result: 64
root@:~/tp# ./eucl_rec -o - 1111 1294
result: 1

\end{verbatim}

\newpage
\section{Analisis del stack}
\subsection{eucl iterativa}

En este caso, primero se arma la parte del stack que corresponde al \textit{main}, y luego al llamar a la funcion \textit{eucl}, se arma el stack que corresponde a esa funcion. Como la funcion \textit{eucl}, es una funcion hoja, no necesita salvar salvar la \textit{return address} porque no se va a modificar al invocarla. \\
Un diagrama del stack seria el siguiente:

\begin{table}[!htp]
\begin{center}
\begin{tabular}{|c|}
\hline
\textbf{main} \\
\hline
argv (4 bytes) \\
\hline
argc=2 (4 bytes)\\
\hline
uint a=5 (4 bytes)\\
\hline
uint b=10 (4 bytes)\\
\hline
uint mcd (4 bytes)\\
\hline
FILE* file (4 bytes)\\
\hline
Unspecified Area (8 bytes)\\
\hline
uint b=10 (4 bytes)\\
\hline
uint a=5 (4 bytes)\\
\hline
\hline
\textbf{eucl}\\
\hline
fp (4 bytes)\\
\hline
gp (4 bytes)\\
\hline
Unspecified Area (8 bytes)\\
\hline
\end{tabular}
\caption{Estado del stack para cuando se invoca a la funcion eucl (iterativa)} \label{tab001}
\end{center}
\end{table}


\newpage
\subsection{eucl recursiva}
Para el caso de la funcion \textit{eucl} recursiva, tambien primero se arma la parte del stack que corresponde al \textit{main}. Luego al llamar a la funcion \textit{eucl}, se arma el stack que corresponde a esa funcion pero esta vez si se necesita salvar la \textit{return address} porque al ser recursiva puede que necesita llamarse a si misma para seguir calculado. Tambien, es necesario que reserve 8 bytes mas para salvar los dos argumentos que necesita la funcion como parametro.

Un diagrama del stack seria el siguiente, usando como parametros desde consola 5 y 10.
\begin{table}[!htp]
\begin{center}
\begin{tabular}{|c|}
\hline
\textbf{main} \\
\hline
argv (4 bytes) \\
\hline
argc=2 (4 bytes)\\
\hline
uint a=5 (4 bytes)\\
\hline
uint b=10 (4 bytes)\\
\hline
uint mcd (4 bytes)\\
\hline
FILE* file (4 bytes)\\
\hline
Unspecified Area (8 bytes)\\
\hline
uint b=10 (4 bytes)\\
\hline
uint a=5 (4 bytes)\\
\hline
\hline
\textbf{eucl} \\
\hline
ra (4 bytes)\\
\hline
fp (4 bytes)\\
\hline
gp (4 bytes)\\
\hline
Unspecified Area (8 bytes)\\
\hline
uint b=5 (4 bytes)\\
\hline
uint a=10 (4 bytes)\\
\hline
\hline
\textbf{eucl} \\
\hline
ra (4 bytes)\\
\hline
fp (4 bytes)\\
\hline
gp (4 bytes)\\
\hline
uint b=0 (4 bytes)\\
\hline
uint a=5 (4 bytes)\\
\hline
\hline
\textbf{eucl} \\
\hline
ra (4 bytes)\\
\hline
fp (4 bytes)\\
\hline
gp (4 bytes)\\
\hline
Unspecified Area (8 bytes)\\
\hline
uint b=Sin inicializar (4 bytes)\\
\hline
uint a=Sin inicializar (4 bytes)\\
\hline
\end{tabular}
\caption{Estado del stack para cuando se invoca a la funcion eucl (recursiva)} \label{tab001}
\end{center}
\end{table}
Puede observarse como esta vez, el tamano total utilizado del stack es mayor, y como crece al hacer la llamada recursiva.

\newpage
\section{Codigo}
\subsection{main.c}

\begin{small}
\begin{verbatim}
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <stdio.h>
#include <stdlib.h>
#include "eucl.h"
#define MAXINT	100

enum error{EXITO,ERROR_PARAM,EXCEDE_RANGO,ARCH_NOCREADO};
FILE *archivo;

void help(){

	char help[]=	"Usage:\n"
			"\teucl -h\n"
			"\teucl -V\n"
			"\teucl [options] M N\n"
			"Options:\n"
			"\t-h, --help		Prints usage information.\n"
			"\t-V, --version	Prints version information.\n"
			"\t-o, --output		Path to output file.\n"
			"Examples:\n"
			"\teucl -o - 256 192\n";
	printf("%s",help);
}

void version(){
	printf("eucl version 0.1\n");
}

int main(int argc, char *argv[]){
	unsigned int a;
	unsigned int b;
	unsigned int mcd;
	FILE* file;
	if(argc <= 1){
		help();
	} else {
		if(argc == 2){
			if( (strcmp(argv[1],"-V")==0) || (strcmp(argv[1],"--version")==0) ){
				version();
			} else if( (strcmp(argv[1],"-h")==0) || (strcmp(argv[1],"--help")==0)){
				help();
			} else {
				printf("eucl: invalid option -- '%s'\n",argv[1]);
				printf("Try `eucl --help' for more information.\n");
			}
		} else if(argc == 5){
			if( (strcmp(argv[1],"-o")==0) || (strcmp(argv[1],"--output")==0)){
				a=atoi(argv[3]);
				b=atoi(argv[4]);
				if (a<2 || a>MAXINT || b<2 || b> MAXINT){
					fprintf(stderr,"ERROR: Numero fuera de rango.\n");	
			 		fclose(archivo);
					return EXCEDE_RANGO;
				}
				mcd=eucl(a,b);
				if((strcmp(argv[2],"-")==0)){
					printf("result: %d\n",mcd);
				} else {
					file=fopen(argv[1],"a");
					if(!file){
						fprintf(stderr,"ERROR: Archivo no pudo ser creado\n");
						return ARCH_NOCREADO;
					}
					fprintf(file,"result: %d\n",mcd);
					fclose(file);

				}
			} else {
				printf("eucl: invalid option -- '%s'\n",argv[1]);
				printf("Try `eucl --help' for more information.\n");
			}
		} else {
			printf("eucl: invalid option -- '%s'\n",argv[1]);
			printf("Try `eucl --help' for more information.\n");
		}
	}
 	return EXITO;
}
\end{verbatim}
\end{small}

\subsection{eucl\_rec.c}
\begin{small}
\begin{verbatim}
#include "eucl.h"

unsigned int eucl(unsigned int a, unsigned int b){
	if(b != 0){
		return eucl(b, a % b);
	} else {
		return a;
	}
}
\end{verbatim}
\end{small}

\subsection{eucl\_it.c}
\begin{small}
\begin{verbatim}
#include "eucl.h"
unsigned int eucl(unsigned int a, unsigned int b){
     	if(a == 0){
	 return b;
	}
     	while(b != 0){
		if (b < a)
			a -=b;
		else
			b -=a;
	}
     	return a;
}
\end{verbatim}
\end{small}

\newpage
\subsection{Assembler \textsl{eucl\_it.s}}

\begin{small}
\begin{verbatim}
	.file	1 "eucl.c"
	.section .mdebug.abi32
	.previous
	.abicalls
	.text
	.align	2
	.globl	eucl
	.ent	eucl
eucl:
	subu	$sp,$sp,16
	sw	$fp,12($sp)		# guarda el fp
	sw	$28,8($sp)		# 28 gp guarda el gp
	move	$fp,$sp
	move	$8,$4			# t0 = a
	move	$9,$5			# t1 = b
	bne 	$8,$0,iterar
	move	$2,$9
	j	end

iterar:	slt	$10,$9,$8		# if(b<a)
	beq	$10,$0,bmaia
	subu	$8,$8,$9
	j	loop

bmaia:	subu	$9,$9,$8
loop:	bne	$0,$9,iterar 
	move	$2,$8
end:	move	$sp,$fp			
	lw	$fp,12($sp)		# levanta el fp
	lw	$fp,8($sp)		# levanta el gp
	addu	$sp,$sp,16
	j	$31
	.end	eucl
	.size	eucl, .-eucl
	.ident	"GCC: (GNU) 3.3.3 (NetBSD nb3 20040520)"

\end{verbatim}
\end{small}

\subsection{Assembler \textsl{eucl\_rec.s}}
\begin{small}
\begin{verbatim}
	.file	1 "eucl.c"
	.section .mdebug.abi32
	.previous
	.abicalls
	.text
	.align	2
	.globl	eucl
	.ent	eucl
eucl:
	subu	$sp,$sp,32
	sw	$31,28($sp)
	sw	$fp,24($sp)
	sw	$28,20($sp)
	move	$fp,$sp
	move	$8,$4			# t0 = a
	move	$9,$5			# t1 = b
	bne	$0,$9,bncero
	move	$2,$8
	j	exit

bncero:	divu	$10,$8,$9
	mfhi	$10
	move	$4,$9
	move	$5,$10
	sw	$4,0($sp)
	sw	$5,4($sp)
	la	$25,eucl
	jal	$31,$25
	

exit:	move	$sp,$fp
	lw	$31,28($sp)
	lw	$fp,24($sp)
	lw	$28,20($fp)
	addu	$sp,$sp,32
	j	$31
	.end	eucl
	.size	eucl, .-eucl
	.ident	"GCC: (GNU) 3.3.3 (NetBSD nb3 20040520)"
\end{verbatim}
\end{small}
\newpage

\section{Conclusiones}
\paragraph{conclucion}
Para hacer las conclusiones, decidimos pasar el codigo del archivo \textit{eucl\_rec.c} y \textit{eucl\_it.c} a codigo assembly de la siguiente manera.\\\\
\texttt{\$gcc -S -o eucl\_itgcc.s eucl\_it.c} \\y\\ \texttt{\$gcc -S -o eucl\_recgcc.s eucl\_rec.c} \\\\
Analizando el codigo assembly de las funciones iterativas y recursivas, se vio que el numero de instrucciones del codigo generado por el ggc era de para la iterativa y la recursiva era de \textbf{54} y \textbf{54}, mientras las instrucciones de nuestro codigo eran \textbf{36} y \textbf{40} respectivamente. Esto no necesariamente significa que nuestro codigo es mas rapido. Para hacer ese analisis, habria que tener en cuenta los lazos que hay en el codigo, de cuantas instrucciones es el lazo, cuantas veces se ejecuta, de que tipo son las instrucciones del lazo, etc. Sin embargo, si puede afirmase que el tamano en memoria de nuestro codigo, es de un 60\% o 75\% del codigo compilado por el gcc.\\
Otra de las diferencias, es que nuestra rutina assembly, no reserva memoria que no sea para almacenar los registros que especifica la convencion (\textit{gp}, \textit{fp}, \textit{ra} (la recursiva)y 8 bytes de \textit{Unspecified Area}). Solamente utiliza registros temporales, mientras que la rutina compilada por el gcc, reserva el doble de memoria.\\
Es claro que para una PC de escritorio, estas diferencias entre los codigos, son inperseptibles. Pero en el caso de un sistema, donde el tamano de la memoria es reducida, estas diferencias pesan. \\
También se pudo observar, que el codigo assembly de la funcion iterativa resulto ser mas corto, y eso sin tener en cuenta que el codigo recursivo se llama a si mismo, cuando a un nivel mas alto (programando en \texttt{C}) el codigo recursivo resultaba mucho mas simple y corto. Ademas, el codigo recursivo tiene el overhead de crear un mayor stack y almacenar los parametros en la pila para la llamada recursiva.

\end{document}

